/* 
 * File:   KNNTraversal.cpp
 * Author: liuyi
 * 
 * Created on October 8, 2009, 11:14 AM
 */

#include "KNNTraversal.h"
#include "Toolkit.h"
#include "Sample.h"
#include "SampleSpace.h"

#include <cfloat>
#include <fstream>

void KNNTraversal::store2File(const char *modelPath) {
    ofstream fout(modelPath);

    m_sampleSpace->store2Stream(fout);

    m_sampleSpace->storeSample2Stream(fout, *m_sampleList);

    fout.close();
}

KNNTraversal * KNNTraversal::loadFromFile(const char *modelPath) throw(FileNotFoundException) {
    ifstream fin(modelPath);
    if(!fin) {
        string filePath(modelPath);
        throw FileNotFoundException(filePath + " does not exits");
    }

    SampleSpace *ss = SampleSpace::loadFromStream(fin);

    KNNTraversal *knn = new KNNTraversal(*ss, true);

    knn->m_sampleList = new vector<Sample *>;
    knn->m_sampleSpace->loadSampleFromStream(fin, *knn->m_sampleList);

    delete ss;

    fin.close();

    return knn;
}

void KNNTraversal::classify(Sample &sample) {
    int size = m_sampleList->size();

    // m_K pieces of nearest neighborhood's distances
    float *nn = new float[m_K];

    for (int i = 0; i < m_K; i++) {
        nn[i] = FLT_MAX;
    }

    // record the m_K pieces of nearest neighborhood's offset in trainingList
    int *recordOff = new int[m_K];

    float distance2;
    bool isAvailable = false;
    for (int index = 0; index < size; index++) {
        isAvailable = m_sampleSpace->distance2(sample, *m_sampleList->at(index), distance2, nn[m_K - 1]);

        if (isAvailable) {
            nn[m_K - 1] = distance2;
            recordOff[m_K - 1] = index;

            for (int i = 1; i < m_K; i++) {
                if (nn[m_K - i] < nn[m_K - i - 1]) {
                    Toolkit::swap(nn, m_K - i, m_K - i - 1);
                    Toolkit::swap(recordOff, m_K - i, m_K - i - 1);
                } else {
                    break;
                }
            }
        }
    }

    int tempROff = recordOff[0]; // record the most nearest

    // Bubble sort, in order to find training samples with the highest appearance in the same class
    for (int i = 0; i < m_K - 1; i++) {
        for (int j = 0; j < m_K - i - 1; j++) {
            if (m_sampleList->at(recordOff[j])->getClass() > m_sampleList->at(recordOff[j + 1])->getClass()) {
                Toolkit::swap(recordOff, j, j + 1);
            }
        }
    }

    int offset = 0, recodeCount = 0, count = 1;
    for (int i = 1; i < m_K; i++) {
        if (m_sampleList->at(recordOff[i])->getClass() == m_sampleList->at(recordOff[i - 1])->getClass()) {
            ++count;
        } else {
            if (count > recodeCount || (count == recodeCount && m_sampleList->at(recordOff[i - 1])->getClass() == m_sampleList->at(tempROff)->getClass())) {
                recodeCount = count;
                offset = recordOff[i - 1];
            }

            count = 1;
        }
    }
    if (count > recodeCount || (count == recodeCount && m_sampleList->at(recordOff[m_K - 1])->getClass() == m_sampleList->at(tempROff)->getClass())) {
        recodeCount = count;
        offset = recordOff[m_K - 1];
    }

    sample.setClass(m_sampleList->at(offset)->getClass());

    delete[] nn;
    delete[] recordOff;
}
